home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 9 / CDACTUAL9.iso / share / Dos / VARIOS / pascal / SWAG9605.DDD / 0038_Fast Primes.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1996-05-31  |  3.1 KB  |  141 lines

  1. {
  2. I have made a program that calculates Primes, I think it is quite
  3. fast and would like to have it included in SWAG.
  4. On a P120 it calculates all primes up to 1.000.000 in 10.3 s.
  5.  
  6. And if somebody knows how to optimize it please tell me. }
  7.  
  8. program prime;
  9.  
  10. uses dos,crt;
  11.  
  12. var      prmtal         : array[1..16142] of longint;
  13.          a              : longint;
  14.          sq,qq,x,tst    : longint;
  15.          h,m,s,hu       : word;    {time}
  16.          xx             : longint;
  17.          b              : word;
  18.          till           : longint;  {check primes up to..}
  19.          g              : string[10];
  20.  
  21.  
  22. procedure Putstr(s:string);assembler;   {This routine was made by}
  23. asm                                     {     JAMIE MORTIMER     }
  24.   push ds
  25.  
  26.   mov ax,$b800
  27.   mov es,ax
  28.   xor di,di
  29.  
  30.   lds si,s
  31.   mov cl,byte ptr [si]
  32.   inc si
  33.   mov ah,7
  34. @1:
  35.   mov al,byte ptr [si]
  36.   mov word ptr es:[di],ax
  37.  
  38.   inc si
  39.   add di,2
  40.   dec cl
  41.   jnz @1
  42.  
  43.   pop ds
  44. end;
  45.  
  46.  
  47. procedure prm1;
  48. begin
  49.   tst:=121;
  50.   repeat
  51.     repeat
  52.       inc(a,4);
  53.       if tst<a then begin
  54.         inc(qq);
  55.         tst:=prmtal[qq]*prmtal[qq];
  56.       end;
  57.       if(a mod 5=0)or(a mod 7=0)or(a mod 11=0)or (a mod 13=0) then break;
  58.       for b:=5 to qq do
  59.         if (a mod prmtal[b])=0 then break;
  60.       if b<(qq)  then break;
  61.       str(a,g);
  62.       putstr(g);
  63.       inc(x);
  64.       prmtal[x]:=a;
  65.     until 1=1;
  66.     repeat
  67.       inc(a,2);
  68.       if (a mod 5 = 0)or (a mod 7=0)or(a mod 11=0)or(a mod 13=0) then break;
  69.       for b:=5 to qq+1 do
  70.         if (a mod prmtal[b])=0 then break;
  71.       if b<qq+1 then break;
  72.       str(a,g);
  73.       putstr(g);
  74.       inc(x);
  75.       prmtal[x]:=a;
  76.     until 1=1;
  77.   until x>16100;
  78.  
  79.   repeat
  80.     repeat
  81.       inc(a,4);
  82.       if tst<a then begin
  83.         inc(qq);
  84.         tst:=prmtal[qq]*prmtal[qq];
  85.       end;
  86.       if (a mod 5 = 0)or (a mod 7=0)or(a mod 11=0)or(a mod 13=0) then break;
  87.       for b:=5 to qq  do
  88.         if (a mod prmtal[b])=0 then break;
  89.       if b<qq then break;
  90.       str(a,g);
  91.       putstr(g);
  92.       inc(x);
  93.     until 1=1;
  94.     repeat
  95.       inc(a,2);
  96.       if (a mod 5 = 0)or (a mod 7=0)or(a mod 11=0)or(a mod 13=0) then break;
  97.       for b:=5 to qq+1 do
  98.         if (a mod prmtal[b])=0 then break;
  99.       if b<qq+1 then break;
  100.       str(a,g);
  101.       putstr(g);
  102.       inc(x);
  103.     until 1=1
  104.   until a>till;
  105. end;
  106.  
  107. begin
  108.   prmtal[16142]:=3;
  109.   xx:=0;
  110.   a:=25;
  111.   qq:=5;
  112.  
  113.   gettime(h,m,s,hu);
  114.   sq:=hu+100*s+6000*m+360000*h;
  115.   prmtal[1]:=5;    {2 and 3 is not included..}
  116.   prmtal[2]:=7;
  117.   prmtal[3]:=11;
  118.   prmtal[4]:=13;
  119.   prmtal[5]:=17;
  120.   prmtal[6]:=19;
  121.   prmtal[7]:=23;
  122.   till:=1000000;
  123.   x:=7;
  124.   clrscr;
  125.  
  126.   prm1;     {begin testing}
  127.  
  128.   writeln;
  129.   Writeln('Primes found:',x,'   ');
  130.   Gettime(h,m,s,hu);
  131.   sq:=(hu+100*s+m*6000+h*360000)-sq;
  132.   writeln('Time ',round(int(sq/100)),'.',round(100*frac(sq/100)),'s');
  133.   writeln;
  134.   writeln(' Dx/33  = 53.34s');
  135.   writeln(' Dx/40  = 43.61s');
  136.   writeln('Dx4/75  = 23.53s');
  137.   writeln('Dx4/100 = 17.67s');
  138.   writeln('Dx4/120 = 14.71s');
  139.   writeln(' P120   = 10.32s');
  140. end.
  141.